package LeetCode.month03.day77;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author 16778
 * @date 2025/10/17 11:55
 * @description
 */
public class No399 {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Union union = new Union(equations.size() * 2);
        Map<String,Integer> map  =new HashMap<>();
        int index = 0;
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            String s1 = equation.get(0);
            String s2 = equation.get(1);
            if (!map.containsKey(s1)) {
                map.put(s1, index++);
            }
            if (!map.containsKey(s2)) {
                map.put(s2, index++);
            }
            union.union(map.get(s1), map.get(s2), values[i]);
        }
        double[] res = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            List<String> equation = queries.get(i);
            String s1 = equation.get(0);
            String s2 = equation.get(1);
            if(!map.containsKey(s1)||!map.containsKey(s2)){
                res[i] = -1.0d;
            }else{
                int index1 = map.get(s1);
                int index2 = map.get(s2);
                if(union.find(index1)!= union.find(index2)){
                    res[i]=-1.0d;
                }else{
                    res[i]= union.weight[index1]/ union.weight[index2];
                }
            }
        }
        return res;
    }

    public class Union{
        int[] parent;
        double[] weight;

        public Union(int n) {
            this.parent = new int[n];
            this.weight = new double[n];
            for (int i = 0; i < n; i++) {
                parent[i]=i;
                weight[i]=1.0d;
            }
        }

        public void union(int x,int y,double value){
            int root1 = find(x);
            int root2 = find(y);
            if(root2==root1){
                return ;
            }
            parent[root1]=root2;
            weight[root1] = weight[y]*value/weight[x];
        }
        public int find(int x){
            if(x!=parent[x]){
                int origin = parent[x];
                parent[x]=find(parent[x]);
                weight[x]*=weight[origin];
            }
            return parent[x];
        }
    }
}
